
/*
Description:
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
*/

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

class Solution {
public:
	vector<vector<int>> combine0(int n, int k) {
		vector<vector<int>> result;
		int i = 0;
		vector<int> p(k, 0);
		while (i >= 0) {
			p[i]++;
			if (p[i] > n) --i;
			else if (i == k - 1) result.push_back(p);
			else {
				++i;
				p[i] = p[i - 1];
			}
		}
		return result;
	}

	/*
	using dfs
	my idea is using backtracking, every time I push a number into vector, then I push a bigger one into it;
	then i pop the latest one, and push a another bigger one...
		and if I has push k number into vector, I push this into result;

	this solution take 24 ms.
	*/

	vector<vector<int> > combine1(int n, int k) {
		vector<vector<int> >res;
		if (n<k)return res;
		vector<int> temp(0, k);
		combine(res, temp, 0, 0, n, k);
		return res;
	}

	void combine(vector<vector<int> > &res, vector<int> &temp, int start, int num, int n, int k) {
		if (num == k) {
			res.push_back(temp);
			return;
		}
		for (int i = start; i<n; i++) {
			temp.push_back(i + 1);
			combine(res, temp, i + 1, num + 1, n, k);
			temp.pop_back();
		}
	}
	/*
	recursive solution C(n,k) ->C(n-1,k-1) / 8ms
	*/
	vector<vector<int>> combine2(int n, int k) {
		vector<vector<int>> ans;
		vector<int> temp;
		combine(1, n, k, ans, temp); //call fuction to get combination of k numbers which range is 1-n
		return ans;
	}
	void combine(int begin, int n, int k, vector<vector<int>> &ans, vector<int>& temp) {
		if (k == 0) {
			ans.push_back(temp);
			return;
		}
		//condition : n-i+1 is the range, range must greater than k
		for (int i = begin; n - i + 1 >= k; i++) { // for the ith iteration, get the combination of i and k-1 numbers differ from i.
			temp.push_back(i);
			combine(i + 1, n, k - 1, ans, temp);// get the combination of k-1 numbers which range is(i+1,n) 
			temp.pop_back();
		}
	}

	//vector<vector<int>> combine(int n, int k) {
	//	vector<vector<int>> c;// = { {2,4},{3,4} };
	//	set<vector<int>> s;
	//	vector<int> t;
	//	vector<int> flag;
	//	flag.resize(n);
	//	for (auto j = 0; j < k; j++)			
	//	{
	//		for (auto i = 1; i <= n; i++)
	//		{
	//			for (auto m = i; m <= n; m++)
	//			{
	//				while (flag.at(m - 1) == 0)
	//				{
	//					t.push_back(m);
	//					flag.at(m - 1) = 1;
	//				}
	//			}
	//			
	//		}
	//	}
	//	return c;
	//}
};

int _combinations()
{
	int n = 4, k = 2;
	Solution solu;
	vector<vector<int>> comb;

	comb = solu.combine2(n, k);

	cout << "n:" << n << " k:" << k << endl;
	cout << "combinations:" << endl;
	for (auto c : comb)
	{
		for (auto v : c)
		{
			cout << v << " ";
		}
		cout << endl;
	}
	cout << endl;
	return 0;
}